package com.syxbyi.yudong.class02;

import java.util.HashMap;

public class SubarraySumK {

    public static int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = 0;
        int N = nums.length;
        HashMap<Integer, Integer> sums = new HashMap<>();
        sums.put(0, 1);         // 先加入一个 0 是因为之后计算的子数组 [i+1,j] 无法考虑到 [0,j] 的情况
        int[] s = new int[N];
        for (int i = 0; i < N; i++) {
            s[i] = nums[i];
            if (i > 0) {
                s[i] += s[i - 1];
            }
            // 满足条件的子数组 sub[i+1, j]，满足 s[j] - s[i] = k, i < j
            // 所以对于每一个位置 j，只需要查表有多少个前缀和为 k - s[j]，即可确定以 j 结尾的 KSum 子数组
            if (sums.containsKey(s[i] - k)) {
                res += sums.get(s[i] - k);
            }
            if (i == N - 1) {           // i 是最后一个位置，不需要再加入前缀和了
                break;
            }
            // 然后将 j 位置作为其他子数组的起始位置 i，加入前缀和到 map 中
            if (sums.containsKey(s[i])) {           // add s[i] to map
                sums.put(s[i], sums.get(s[i]) + 1);
            } else {
                sums.put(s[i], 1);
            }
        }
        return res;
    }

}
